#include <iostream>
#include <vector>

using namespace std;

const int n=5;
const int m=6;
const int inf=9999;                    //La valeur infinie.    


void initDist(int dist[][n])
{

	for(int i=0; i<n ; i++)
	{
		for(int j=0; j<n; j++)
		{
			dist[i][j]=inf;
		}
	}
	
}

void initChemin(int chemin[][n], int longueur[][n])
{

	for(int i=0; i<n ; i++)
	{
		for(int j=0; j<n; j++)
		{
			if(longueur[i][j]!=-1)
				chemin[i][j]=j;
			else
				chemin[i][j]=-1;
		}
	}
	
}

void floyd_warshall(int longueur[][n], int dist[][n], int chemin[][n])
{

	for(int i=0; i<n ; i++)
	{
		for(int j=0; j<n; j++)
		{
			if(longueur[i][j]!=inf)
				dist[i][j]=longueur[i][j];
			
		}
	}
	
	for(int k=0; k<n ; k++)
	{
		for(int i=0; i<n; i++)
		{
			for(int j=0; j<n; j++)
			{
				if(dist[i][j]>dist[i][k]+dist[k][j])
				{
					dist[i][j]=dist[i][k]+dist[k][j];
					chemin[i][j]=chemin[i][k];
				}
			
			}
			
		}
	}
	
	
	
}

void affichage(int tab[][n])
{
		for(int i(0); i<n; i++)
		{
		
			for(int j(0); j<n; j++)
			{
				if(tab[i][j]!=inf && tab[i][j]!=-1)	
					cout<<"longueur de "<<i<<" a "<<j<<" : "<<tab[i][j]<<endl;
			}
		}
	
}


void itineraire(int i, int j, int chemin[][n])
{
	cout<<i<<" ";
	if(i==j)
		cout<<i<<" "<<endl;
	else
	{
		if(chemin[i][j]== j)
			cout<<j<<" "<<endl;

		else 
		{
			//cout<<i<<chemin[i][j];
			itineraire(chemin[i][j], j, chemin);

		}
	}



}

void matriceAdj(int longueur[][m], int arc[][m])
{
	for(int i(0); i<n;i++)
	{
		for(int j(0); j<n;j++)
		{
			if((longueur[i][j]!=inf)&&(longueur[i][j]!=0))
				arc[i][j]=1;
			else
				arc[i][j]=0;
		}
		
	}
	
	
	
}



void fermetureTransitive(int arc[][m], int fermeture[][m])
{
	
	for(int i=0; i<m ; i++)
	{
		for(int j=0; j<m; j++)
		{
			
			fermeture[i][j]=arc[i][j];
			
		}
	}
	
	
	
	
	
	for(int k=0; k<m ; k++)
	{
		for(int i=0; i<m; i++)
		{
			for(int j=0; j<m; j++)
			{
				if(i==j)
					fermeture[i][j]=1; 
				else if(arc[i][j]==0)
				{
					if((arc[i][k]==1 && arc[k][j]==1)|| (fermeture[i][k]==1 && fermeture[k][j]==1) )
						fermeture[i][j]=1; 
				}
			
			}
			
		}
	}
	
	
}


void affichageMatrice(int mat[][m])
{
	
	for(int j=0; j<m; j++)
	{
		for(int i=0; i<m; i++)
		{
			cout<<mat[j][i]<<" ";
			
		}
		cout<<endl;
			
	}
	
}

void fortConnexe(int p, vector<int>  comp[m], int dv[m], vector<int> &connexe)
{
	
	for(int i=0; i<comp[p].size(); i++)
	{
		if(comp[p]==comp[comp[p][i]])
		{
			//cout<<i<<endl<<p<<endl<<endl;	
			dv[comp[p][i]]=1;
			connexe.push_back(comp[p][i]);
				
		}
	}
	
	
	dv[p]=1;
	
	
}


void compfortconnexe(int fermeture[][m])
{
	vector<int>  comp[m];
	vector<int> connexe[m];
	int dv[m];
	
	for(int i=0; i<m; i++)
	{
		dv[i]=0;
	}
	
	
	
	
	for(int i=0; i<m; i++)
	{
		for(int j=0; j<m; j++)
		{
			if(fermeture[i][j]==1)
			{
				
					comp[i].push_back(j);				
			}	
			
		}
		
	}
	
	
	
	for(int i=0; i<m; i++)
	{
		if(dv[i]==0)
		{
			fortConnexe(i, comp, dv, connexe[i]);
		}
		
	}
	
	
	
	for(int i=0; i<m; i++)
	{
		if(connexe[i].size()>0)
		{
			
			cout<<"{";
			for(int j=0; j<connexe[i].size(); j++)
			{
				cout<<" "<<connexe[i][j]+1;
				
								
			}
			
			cout<<" }"<<endl;;		
		}
		
	}
	
	
}





int main(){

  int longueur[n][n]={{0,2,inf,4,inf}, //Les longueurs des arcs.
                  {inf,0,2,inf,inf},   //long[i][j]=inf si l'arc ij n'existe pas
                  {inf,inf,0,2,inf},
                  {inf,-3,inf,0,2},
                  {2,inf,inf,inf,0}};                
  int dist[n][n];                      //Le tableau des distances.
  int chemin[n][n];    //Le tableau de la premiere etape du chemin de i a j.
  int arc[m][m]={{0,0,0,1,0,1}, 
                 {1,0,1,1,0,0}, 
                 {0,0,0,1,0,0},
                 {0,0,0,0,1,1},
	       {0,0,1,0,0,1},
                 {0,0,1,0,0,0}}; 
  int fermeture[m][m];
  
 initDist(dist);
 initChemin(chemin,longueur);
 floyd_warshall(longueur,dist,chemin);
// matriceAdj(longueur, arc);
 fermetureTransitive(arc,fermeture);
 affichageMatrice(arc);
 
 cout<<endl;
 affichageMatrice(fermeture);
  cout<<endl;
 compfortconnexe(fermeture);
 //affichage(chemin);
//  int i;
// int j;
// cout<<"saisir un point de départ"<<endl;
// cin>>i;
// cout<<"saisir un point d'arrivée"<<endl;
// cin>> j;
// 
// itineraire(i, j, chemin);
//  
 //affichage(dist);



return 0;
}


